const long inf = 1e15, MOD = 1e9 + 7;
class Solution {
public:
    class greater{
    public:
        bool operator()(pair<int,long>& a,pair<int,long>& b){
            return a.second > b.second;
        }
    };
    int countPaths(int n, vector<vector<int>>& roads) {
        vector<vector<pair<int,int> > > edges(n);
        for(auto& vc : roads){
            edges[vc[0]].push_back({vc[1],vc[2]});
            edges[vc[1]].push_back({vc[0],vc[2]});
        }
        
        vector<int> vis(n,0);
        vector<int> f(n,0);
        vector<long> dist(n,inf);
        dist[0] = 0;
        f[0] = 1;
        
        priority_queue<pair<int,long>,vector<pair<int,long> > ,greater> pri_que;
        pri_que.push({0,0});
        
        
        while(!pri_que.empty()){
            auto kv = pri_que.top();
            pri_que.pop();
            
            int u = kv.first;
            if(vis[u]){
                continue;
            }
            vis[u] = 1;
            
            for(auto& [v, w] : edges[u]) {
                if(dist[v] > dist[u] + w) {
                    f[v] = f[u];
                    dist[v] = dist[u] + w;
                    pri_que.push( {v,dist[v]} );
                }
                else if(dist[v] == dist[u] + w) {
                    f[v] = (f[v] + f[u]) % MOD;
                }
            }
        }
       return f[n-1];
    }
};
